package class04;

import java.util.ArrayList;
import java.util.HashMap;

// 题目描述：
// 给定一个数组arr，然后给定一个数字value，查询在数组的区间[L,R]范围内，value出现了几次
// 例如：数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)。意思是在数组里下标0~3这个范围上，有几个2？返回2。
// 假设给你一个数组arr，对这个数组的查询非常频繁，请返回所有查询的结果
//
// 解题思路：
// 本题提供了两种解决方案：
// 方法一：QueryBox1 - 暴力解法
// 直接遍历区间内的每个元素，统计目标值的出现次数。时间复杂度O(R-L+1)，适合查询不频繁的场景。
//
// 方法二：QueryBox2 - 优化解法（推荐）
// 利用预处理和二分查找优化查询效率：
// 1. 预处理阶段：建立值到下标列表的映射关系，相同值的所有下标构成一个有序列表
// 2. 查询阶段：对于查询(L,R,value)，在value对应的下标列表中，使用二分查找找出
//    小于L的下标个数a和小于R+1的下标个数b，则区间[L,R]中value的个数为b-a
// 时间复杂度：预处理O(N)，每次查询O(logN)，适合查询频繁的场景。
public class Code01_QueryHobby {

	/*
	 * 今日头条原题
	 * 
	 * 数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)。意思是在数组里下标0~3这个范围上，有几个2？返回2。
	 * 假设给你一个数组arr，对这个数组的查询非常频繁，请返回所有查询的结果
	 * 
	 */

	// 方法一：暴力解法
	public static class QueryBox1 {
		// 存储原始数组的副本
		private int[] arr;

		// 构造函数，初始化数组
		public QueryBox1(int[] array) {
			arr = new int[array.length];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = array[i];
			}
		}

		// 查询区间[L,R]内值为v的元素个数
		public int query(int L, int R, int v) {
			// 计数器初始化为0
			int ans = 0;
			// 遍历区间[L,R]内的每个元素
			for (; L <= R; L++) {
				// 如果当前元素等于目标值v，则计数器加1
				if (arr[L] == v) {
					ans++;
				}
			}
			// 返回计数结果
			return ans;
		}
	}

	// 方法二：优化解法（利用预处理和二分查找）
	public static class QueryBox2 {
		// 建立值到下标列表的映射关系，相同值的所有下标构成一个有序列表
		private HashMap<Integer, ArrayList<Integer>> map;

		// 构造函数，预处理数组建立映射关系
		public QueryBox2(int[] arr) {
			map = new HashMap<>();
			// 遍历数组中的每个元素
			for (int i = 0; i < arr.length; i++) {
				// 如果当前值还没有在map中记录过，则创建一个新的ArrayList
				if (!map.containsKey(arr[i])) {
					map.put(arr[i], new ArrayList<>());
				}
				// 将当前元素的下标添加到对应值的列表中
				map.get(arr[i]).add(i);
			}
		}

		// 查询区间[L,R]内值为value的元素个数
		public int query(int L, int R, int value) {
			// 如果查询的值在数组中不存在，直接返回0
			if (!map.containsKey(value)) {
				return 0;
			}
			// 获取目标值对应的所有下标列表
			ArrayList<Integer> indexArr = map.get(value);
			// 查询 < L 的下标有几个
			int a = countLess(indexArr, L);
			// 查询 < R+1 的下标有几个
			int b = countLess(indexArr, R + 1);
			// 区间[L,R]中目标值的个数等于两者的差值
			return b - a;
		}

		// 在有序数组arr中，用二分的方法数出<limit的数有几个
		// 也就是用二分法，找到<limit的数中最右的位置
		private int countLess(ArrayList<Integer> arr, int limit) {
			// 初始化二分查找的左右边界
			int L = 0;
			int R = arr.size() - 1;
			// 记录小于limit的最右位置
			int mostRight = -1;
			// 二分查找过程
			while (L <= R) {
				// 计算中间位置（避免溢出的写法）
				int mid = L + ((R - L) >> 1);
				// 如果中间位置的值小于limit
				if (arr.get(mid) < limit) {
					// 更新最右位置
					mostRight = mid;
					// 在右半部分继续查找
					L = mid + 1;
				} else {
					// 在左半部分继续查找
					R = mid - 1;
				}
			}
			// 返回小于limit的数的个数
			return mostRight + 1;
		}

	}

	// 生成随机数组用于测试
	public static int[] generateRandomArray(int len, int value) {
		// 随机生成数组长度
		int[] ans = new int[(int) (Math.random() * len) + 1];
		// 填充随机值
		for (int i = 0; i < ans.length; i++) {
			ans[i] = (int) (Math.random() * value) + 1;
		}
		return ans;
	}

	// 主函数，用于测试两种方法的正确性
	public static void main(String[] args) {
		// 设置测试参数
		int len = 300;
		int value = 20;
		int testTimes = 1000;
		int queryTimes = 1000;
		System.out.println("test begin");
		// 进行多次测试
		for (int i = 0; i < testTimes; i++) {
			// 生成随机数组
			int[] arr = generateRandomArray(len, value);
			int N = arr.length;
			// 创建两种查询对象
			QueryBox1 box1 = new QueryBox1(arr);
			QueryBox2 box2 = new QueryBox2(arr);
			// 进行多次查询测试
			for (int j = 0; j < queryTimes; j++) {
				// 随机生成查询区间和目标值
				int a = (int) (Math.random() * N);
				int b = (int) (Math.random() * N);
				int L = Math.min(a, b);
				int R = Math.max(a, b);
				int v = (int) (Math.random() * value) + 1;
				// 比较两种方法的结果是否一致
				if (box1.query(L, R, v) != box2.query(L, R, v)) {
					System.out.println("Oops!");
				}
			}
		}
		System.out.println("test end");
	}

}
